#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


int maxSum(int A[], int size)
{
    int maxS = -100000;
    int curSum = 0;
    for (int i = 0; i < size; i++) {
	curSum += A[i];
        if (curSum > maxS) {
	    maxS = curSum;
	}
        if (curSum < 0) {
	    curSum = 0;
	}

    }
    return maxS;
}


int main(int argc, char **argv)
{
     
    cout << "-----------------Test 1--------------------" << endl;
    int A[] = {1,3,5,6,-1,-6,-7,4,-6,-9,10,1,15,-9};
    cout << "maximum sum is " << maxSum(A, sizeof(A)/sizeof(int)) << endl;

    cout << "-----------------Test 2--------------------" << endl;
    int B[] = {-1,-2,-4,-6,-45,-9,-45,-9};
    cout << "maximum sum is " << maxSum(B, sizeof(B)/sizeof(int)) << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
